/*
 * @lc app=leetcode.cn id=130 lang=javascript
 *
 * [130] 被围绕的区域
 */

// @lc code=start
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function (board) {
  const rows = board.length;
  const columns = board[0].length;

  const inArea = (row, column) => {
    return row >= 0 && row < rows && column >= 0 && column < columns;
  };

  const dfs = (row, column, target, pattern) => {
    if (!inArea(row, column) || board[row][column] != "O") return;
    if (board[row][column] === target) board[row][column] = pattern;

    dfs(row - 1, column, target, pattern);
    dfs(row + 1, column, target, pattern);
    dfs(row, column - 1, target, pattern);
    dfs(row, column + 1, target, pattern);
  };

  // 从外层给O染色
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < columns; j++) {
      if (
        (i === 0 || i === rows - 1 || j === 0 || j === columns - 1) &&
        board[i][j] === "O"
      ) {
        dfs(i, j, "O", "A");
      }
    }
  }

  //把内层的O染成X，把A染成O
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < columns; j++) {
      if (board[i][j] === "O") board[i][j] = "X";
      if (board[i][j] === "A") board[i][j] = "O";
    }
  }
};
// @lc code=end
